package graph;

import java.util.HashSet;
import java.util.Vector;

/**
 * O(v+e),tested
 * 
 * @author yinzichen
 * 
 */
class TarjanBCCPoint {
	Vector<HashSet<Integer>> adj;
	int[] islands;// if islands[u] > 1 then u is a articulation point
	int[] used;
	int[] num;
	int[] low;
	int id;

	public int[] articulationPoint(Vector<HashSet<Integer>> bidirectedGraph) {
		int n = bidirectedGraph.size();
		adj = bidirectedGraph;
		islands = new int[n];
		used = new int[n];
		num = new int[n];
		low = new int[n];
		id = 0;
		for (int i = 0; i < n; ++i) {
			if (used[i] == 0) {
				dfs(i);
			}
		}
		return islands;
	}

	private int dfs(int u) {
		num[u] = id;
		low[u] = id++;
		used[u] = 1;
		for (int v : adj.get(u)) {
			if (used[v] == 0) {
				islands[v]++;
				int f = dfs(v);
				if (f >= num[u]) {
					islands[u]++;
				}
				low[u] = Math.min(low[u], f);
			} else if (used[v] == 1) {
				low[u] = Math.min(low[u], num[v]);
			}
		}
		used[u] = 2;
		return low[u];
	}
}
